package org.pupil.sort.mergeSort;

import java.io.*;

/**
 * @Description: 归并排序 ACM算法模式写法
 * 时间复杂度：O(n * logn)
 * 需要辅助数组，所以额外空间复杂度：O(n)
 * 归并排序为什么比O(n^2)的排序快？因为比较行为没有浪费！ O(n^2)的排序通过大量比较才确定一个数
 * @Author: pupil
 * @Date: 2024/08/13 下午 2:03
 */
public class MergeSort {

    // 题目没有说数据量，按道理是要说的
    // 根据实验，长度500以内够用了
    // 如果有一天牛客升级了数据量导致出错
    // 把这个值改大就好
    public static int MAXN = 501;

    // 存储测试数据
    public static int[] arr = new int[MAXN];

    // 辅助数组
    public static int[] help = new int[MAXN];

    // 数组长度
    public static int n;

    public static void main(String[] args) throws IOException {
        // 把文件里的内容，load进来，保存在内存里，很高效，很经济，托管的很好
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 一个一个读数字
        StreamTokenizer in = new StreamTokenizer(br);
        // 提交答案的时候用的，也是一个内存托管区
        PrintWriter printWriter = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) { // 文件没有结束就继续
            n = (int) in.nval; // 行
            for (int i = 0; i < n; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            mergeSort1(0, n - 1);
        }
    }


    // 归并排序递归版
    // 假设l...r一共n个数
    // T(n) = 2 * T(n/2) + O(n)
    // a = 2, b = 2, c = 1
    // 根据master公式，时间复杂度：O(n * logn)
    // 空间复杂度 O(n)
    public static void mergeSort1(int l, int r) {
        if (l == r) {
            return;
        }

        // 获取中间值
        int m = l + ((r - l) >> 1);
        mergeSort1(l, m);
        mergeSort1(m + 1, r);
        merge(l, m, r);
    }

    // 归并排序非递归版
    // 时间复杂度O(n * logn)
    // 空间复杂度O(n)
    public static void mergeSort2() {
        // 一共发送O(logn)次
        for (int l, m, r, step = 1; step <= n; step <<= 1) {
            // 内部分组merge，时间复杂度O(n)
            l = 0; // 左边界
            while (l < n) {
                m = l + step - 1; // 中间位置
                if (m + 1 >= n) {
                    // 已经没有右侧了
                    break;
                }
                // 有右侧，求右侧的右边界
                r = Math.min(l + (step << 1), n - 1);
                // l...m m+1...r
                //                  l...m m+1...r
                //                                  l..m m+1..r
                merge(l, m, r);
                l = r + 1;
            }
        }
    }

    // 归并
    // l....r一个n个数
    // 时间复杂度：O(n)
    // merge过程：谁小拷贝谁，直到左右两个部分所有的数字耗尽，拷贝回原数组
    private static void merge(int l, int m, int r) {
        int i = l; // 辅助数组开始位置
        int a = l; // 左侧开始位置
        int b = m + 1; // 右侧开始位置

        // 开始比较大小
        // 时间复杂度：O(n)
        while (a <= m && b <= r) {
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }

        // 左侧指针、右侧指针，必有一个越界、另一个不越界
        // 这两个只执行其中的一个
        // 时间复杂度：O(n)
        while (a <= m) {
            help[i++] = arr[a++];
        }
        while (b <= r) {
            help[i++] = arr[b++];
        }

        for (i = l; i <= r; i++) {
            arr[i] = help[i];
        }
    }
}
